// 递归
// 本质是：解决主问题时，发现相同子问题，解决主问题和子问题的方法相同 (主问题有可能就是子问题)
// 心理暗示：宏观看待递归问题，把递归函数当成黑盒，相信这个黑盒一定能完成任务
// 技巧：
//      找到重复子问题 -> 设计函数头
//      子问题是如何解决的 -> 函数体的书写
//      注意递归函数的出口 -> 关注问题不能分割的情况
// 拓展：如果一个题目可以用决策树画出来，那么也可以通过递归解决
// 二叉搜索树要用中序遍历去做
// 当 dfs 要做的事情较多时，可以定义全局变量帮助解决问题

// 例题 5：
// 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
//
//        示例 1：
//
//
//        输入：root = [3,1,4,null,2], k = 1
//        输出：1
//        示例 2：
//
//
//        输入：root = [5,3,6,2,4,null,null,1], k = 3
//        输出：3
//
//
//
//
//        提示：
//
//        树中的节点数为 n 。
//        1 <= k <= n <= 104
//        0 <= Node.val <= 104
//
//
//        进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

// 解题思路：
// 二叉搜索树的中序遍历是有序数组，可以使用中序遍历搜索
// 利用全局变量进行计数，利用全局变量标记目标节点
// 二叉树的中序遍历

public class KthSmallest {
    int count = 0;
    TreeNode ret = null;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        dfs(root);
        return ret.val;
    }
    public void dfs(TreeNode root){
        if(root == null) return;
        dfs(root.left);
        count++;
        if(count == 0){
            ret = root;
            return;
        }
        dfs(root.right);
    }
}
